Fuchs từng là thành viên đội U-17 Áo đứng hạng ba tại giải bóng đá U-17 châu Âu năm 2003. Ngày 23 tháng 5 năm 2006, anh có trận đấu đầu tiên cho đội tuyển Áo trong trận giao hữu với Croatia.

Tại Euro 2008, giải đấu mà Áo là nước chủ nhà, Fuchs có cơ hội được ra sân một lần trong trận đấu cuối cùng của vòng bảng với Đức. Ngày 11 tháng 8 năm 2010, Fuchs lần đầu tiên được làm đội trưởng đội tuyển Áo trong trận giao hữu thua Thụy Sĩ 0-1 tại Klagenfurt.[13] Ngày 17 tháng 11, anh ghi bàn thắng đầu tiên trong màu áo đội tuyển, gỡ hòa 1-1 trong trận giao hữu thua Hy Lạp 2-1.[14]

Tại vòng loại Euro 2016, Fuchs góp mặt trong tất cả các trận đấu và Áo chỉ để thủng lưới 5 bàn sau 10 trận và có đến 6 trận giữ sạch lưới để chính thức có mặt tại Euro 2016 với vị trí nhất bảng.[15] Fuchs được triệu tập vào đội hình đội tuyển Áo tham dự Euro 2016 và anh cũng là đội trưởng đội tuyển nước này tại giải đấu.[16] Fuchs có mặt trong cả ba trận đấu vòng bảng với Hungary, Bồ Đào Nha và Iceland. Đội tuyển Áo đã rời giải ngay sau vòng bảng với chỉ vỏn vẹn 1 điểm, đứng cuối bảng F với 1 trận hòa và 2 trận thua, chỉ ghi được 1 bàn thắng và bị thủng lưới 4 bàn. Sau Euro 2016, Fuchs cũng tuyên bố kết thúc sự nghiệp thi đấu quốc tế ở cấp độ đội tuyển quốc gia, tổng cộng anh đã 78 lần khoác áo đội tuyển quốc gia.[17]